



		VIZITA ORASULUI - SOLUTIE
	       ---------------------------

(data de Dumitru Bogdan)

	Aceasta este o problema clasica de grafuri: determinarea ciclului
de lungime minima intr-un graf neorientat.
	Observam mai intai ca, daca intre doua noduri sunt mai multe muchii,
nu vom folosi niciodata doua dintre ele in alcatuirea ciclului cerut (pentru
ca daca le-am folosi, ar insemna ca ciclul sa fie alcatuit numai din acele 2
noduri, deoarece trebuie sa fie elementar; dar acest lucru contravine condi-
tiei din enunt k>2 - ciclul trebuie sa fie format din cel putin trei noduri).
Deducem deci ca, daca intre doua noduri exista mai multe muchii o retinem doar
pe cea de cost minim.
	Vom determina intai ciclul de lungime minima care contine neaparat nodul
1, apoi ciclul de lungime minima care contine neaparat nodul 2 si vom continua
pana la nodul N. Minimul acestor cicluri va constitui, evident, solutia problemei.
	Cum determinam ciclul de lungime minima care trece prin nodul I? Conside-
ram un nod arbitrar J de pe acest ciclu, vom putea scrie ciclul ca reuniune a 2
drumuri de la I la J, drumuri ce nu au in comun decat nodurile I si J. Evident,
unul din aceste drumuri are costul egal cu cel al drumului minim de la I la J
(altfel,ar putea fi substituit cu acesta, costul ciclului minim devenind mai mic).
Celalalt drum este "al doilea drum minim" care are costul cel putin egal cu al
primului. Considerand acest al doilea drum minim ca o reuniune de drumuri (fie
numarul acestora K), el va fi format din K-1 drumuri optime (minime) si un drum
de cost cel putin egal cu al drumului minim corespunzator. Ideea ce se contureaza
este urmatoarea: aplicam algoritmul lui Dijkstra, avand ca nod sursa nodul I.
Acest algoritm determina drumurile minime de la nodul I la celelalte noduri,dru-
muri ale caror reuniune formeaza un arbore cu radacina I (acest lucrue este
evident - legaturile de tip "tata" care sunt construite de acest algoritm gene-
reaza, la reconstituire, un arbore). In afara arborelui creat raman, evident,
M-(N-1)=<-N+1 muchii (unde M era numarul initial de muchii). Se considera oricare
asemenea muchie si ciclul format de ea impreuna cu drumurile minime de la cape-
tele ei pana la radacina arborelui. In cazul in care costul unui asemenea ciclu
este mai mic decat costul ciclului optim, atunci acesta este actualizat.

Complexitate: O(N^3).
